//最长回文子串
//测试链接 https://leetcode.cn/problems/longest-palindromic-substring/description/
public class LongestPalindrome {
    public String longestPalindrome(String s) {
        int n = s.length();
        int max = 1;
        String ret = s.substring(0,1);
        for(int i = 0; i < n; i++){ //以i位置作为中心点往两边寻找最长回文串
            char temp = s.charAt(i);

            //向左边寻找和当前相同的字符
            int left = i, right = i;
            while(left-1 >= 0 && temp == s.charAt(left-1)){
                left--;
            }
            //向右边寻找是否有相同的字符
            while(right+1 < n && temp == s.charAt(right+1)){
                right++;
            }
            //左右同时寻找
            while(left-1 >= 0 && right+1 < n && s.charAt(left-1) == s.charAt(right+1)){
                left--;
                right++;
            }
            if(right - left + 1 > max){
                ret = s.substring(left,right+1);
                max = right - left + 1;
            }
        }
        return ret;
    }
}
